package com.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.Stack;

/**
 * Created by gerrie on 13/06/2019.
 */

public class Leetcode {

    public int numSquares(int n) {
        List<Integer> powers = findNums(n);
        int sum = 0;
/*        Queue<Integer> ps = new LinkedList<>(powers);
        LinkedList<Integer> next = new LinkedList<>();
        int layer_count = 0;
        while (ps.size()!=0){
            int p = ps.poll();
            int cur_sum = sum + p;
            if(cur_sum == n)
                return layer_count;
            else if(cur_sum > n)
                continue;
            else{
                next.addAll(powers);
            }
            if(ps.isEmpty()){
                layer_count ++;

            }
        }*/
        return constructTree(powers, n);
    }
    static class TreeNode{
        public TreeNode parent;
        public List<TreeNode> children = new LinkedList<>();
        public int v;
        TreeNode(int i, TreeNode parent){
            v = i;
            this.parent = parent;
        }
    }
    private int constructTree(List<Integer> ps, int target){
        TreeNode root = new TreeNode(0, null);
        LinkedList<TreeNode> psn = new LinkedList<>();
        LinkedList<TreeNode> next = new LinkedList<>();
        for (Integer p: ps) {
            psn.add(new TreeNode(p, root));
        }
        int levelCount = 0;
        while (!psn.isEmpty() ){
            levelCount ++;
            while (!psn.isEmpty()){
                TreeNode n = psn.poll();
                TreeNode ni = n;
                int sum = 0;

                while(n!=null){
                    sum += n.v;
                    n = n.parent;
                }
                if(sum == target)
                    return levelCount;
                else if(sum > target)
                    continue;
                for (Integer p:ps) {
                    next.add(new TreeNode(p, ni));
                }
            }
            LinkedList<TreeNode> tmp = psn;
            psn = next;
            next = tmp;
        }
        return 0;
    }

    public List<Integer> findNums(int n){
        double m = Math.sqrt(n);
        ArrayList powers = new ArrayList();
        for (int i = (int)m; i > 0; i--) {
            powers.add(i*i);
        }
        return powers;
    }


    static class Node{
        Node parent;
        String word;
        List<Node> children;
        Node(String word, Node p){
            parent = p;
            this.word = word;
        }
    }
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //Fri Jun 14 22:51:46 CST 2019
        //end : Fri Jun 14 23:27:07 CST 2019
        Node root = new Node(null, null);
        LinkedList<Node> current = new LinkedList<>();
        LinkedList<Node> next = new LinkedList<>();
        for(String word:wordList){
            if(isNeighbour2(beginWord, word))
                current.add(new Node(word, root));
        }
        int level = 1;
        while(current.size()!=0){
            level ++;
            while(current.size()!=0){
                Node n = current.poll();
                if(n.word.equals(endWord))
                    return level;
                Node ni = n.parent;boolean isTested = false;
                while(ni!= null){
                    if(ni.word!=null && ni.word.equals(n.word))
                        isTested = true;
                    ni = ni.parent;
                }
                if(isTested)continue;
                for(String word: wordList)
                    if(isNeighbour2(n.word, word))
                        next.add(new Node(word, n));

            }
            LinkedList<Node> tmp = current;
            current = next;
            next = tmp;
        }
        return 0;
    }
    private boolean isNeighbour(String a, String b){
        if(a.length()!= b.length())
            return false;
        int count = 0;
        for (int i = 0; i < a.length(); i++) {
            count += a.charAt(i) == b.charAt(i)? 0 : 1;
        }
        return count == 1;
    }

    HashMap<String, Set<String>> nTabel = new HashMap<>();
    private void createNeighbourMark(String s){
        Set<String> tabel = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            StringBuilder t = new StringBuilder(s);
//            t.charAt(i)
            for(char cc = 'a'; cc <='z'; cc++){
                t.setCharAt(i, cc);
                tabel.add(t.toString());
            }
        }
        nTabel.put(s, tabel);
    }
    private boolean isNeighbour2(String a, String b){
        if(!nTabel.keySet().contains(a)){
            createNeighbourMark(a);
        }
        return nTabel.get(a).contains(b);
    }

    boolean [][]mark ;
    static class Coord{
        int x, y;
        Coord(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public int maxAreaOfIsland(int[][] grid) {
        mark = new boolean[grid.length][grid[0].length];

        int maxArea = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == 0 || mark[i][j])
                    continue;
                Stack<Coord> stack = new Stack<>();
                stack.push(new Coord(j, i));
                int area = dfsIsland(grid, j, i, stack, new int[]{0});
                maxArea = Math.max(maxArea, area);

            }
        }
        return maxArea;
    }
    private int dfsIsland(int [][]grid, int x, int y, Stack<Coord> stack, int []count ){
        while(!stack.isEmpty()){
            Coord c = stack.peek();
            count[0] ++;
            mark[c.y][c.x] = true;
//            for(Coord neighbour: new Coord[]{ new Coord(c.x-1, c.y), new }){
            for(int []arr: new int [][]{{c.x-1, c.y}, {c.x+1, c.y}, {c.x, c.y-1}, {c.x, c.y+1}}){
                Coord neighbour = new Coord(arr[0], arr[1]);
                int cx = neighbour.x, cy = neighbour.y;
                if(!islandisEdge(cx, cy, grid) && !mark[cy][cx]){
                    stack.push(new Coord(cx, cy));
                    dfsIsland(grid, cx, cy, stack, count);
                }
            }
            stack.pop();
        }
        return count[0];
    }

    private int dfsIsland2(int [][]grid, Stack<Coord> stack, int count){
        return 0;
    }

    private int n;
    public int findCirclueNum(int [][]M){
        n = M.length;
        int [][]visited = M.clone();
        return 0;
    }

    private int friendDfs(int [][]M, int [][]visited, int x, int y){
        return 0;
    }


    private boolean islandisEdge(int x, int y, int [][]grid){
        return x< 0 || y < 0 || y >= grid.length || x >=grid[0].length;
    }

    public int[] productExceptSelf(int []nums){
        int []leftProduct = nums.clone();
        int []rightProduct = nums.clone();
        leftProduct[0] = 1;
        leftProduct[1] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            leftProduct[i] = leftProduct[i-1] * nums[i-1];
        }
        rightProduct[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            rightProduct[i] = rightProduct[i-1] * rightProduct[i-1];
        }
        int []result = nums.clone();
        for (int i = 0; i < nums.length; i++) {
            result[i] = leftProduct[i] * rightProduct[i];
        }
        return result;
    }

    /**
     * 为什么是一个下标?为什么不是两个?
     */
    public String addBinary1(String a, String b){
        int lenDiff = a.length() - b.length();
        if(lenDiff < 0){
            String t = a;
            a = b;
            b = t;
            lenDiff = -lenDiff;
        }
        char []arr = new char[lenDiff];
//        Arrays<Character>.fill(arr,'0');
        for (int i = 0; i < arr.length; i++) {
            arr[i] = '0';
        }
        String zeros = new String(arr);
        b = zeros + b;
        StringBuilder result = new StringBuilder();
        int carry = 0;
        for (int i = a.length() - 1; i >= 0; i++) {
//            if(a.charAt(i))
            int sum = (a.charAt(i) == '1'?1:0) + (b.charAt(i) =='1'?1:0) + carry;
            carry = sum/2;
            sum = sum%2;
            result.append(sum);
        }
        if(carry==1)
            result.append("1");
        System.out.println(result.toString());
        return result.toString();
    }
}
